package leetcode;

import java.util.Stack;

public class IsValidKuohao {

	public static void main(String[] args) {
		System.out.println(isValid("({()}))"));
	}
	public static boolean isValid(String s) {
        if(s == null){
            return true;
        }
        boolean flag = true;
        Stack<Character> stack = new Stack<Character>();
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            if(chars[i] == '(' || chars[i] == '[' || chars[i] == '{'){
                stack.push(chars[i]);
                continue;
            }
            if((chars[i] == ')' || chars[i] == ']' || chars[i] == '}') ){
            	flag = false;
				if (!stack.isEmpty()) {
					if (isMatcher(stack.peek(), chars[i])) {
						stack.pop();
						flag = true;
					} else {
						System.out.println("chars[i] " + stack.peek() + " "
								+ chars[i]);
						return false;
					}
				}
            }
        }
        return flag && stack.isEmpty();
    }
	public static boolean isMatcher(char left, char right){
		if(left == '('){
			return right == ')';
		}
		if(left == '['){
			return right == ']';
		}
		if(left == '{'){
			return right == '}';
		}
		return false;
	}
}
